
class Vertex(object):
    def __init__(self, point):
        super(Vertex, self).__init__()
        self.point = point
        self.edge = None

    def edges(self):
        o = e = self.edge
        if e is not None:
            
            yield e
            e = e.twin_edge.next_edge
            
            while e != o:
                yield e
                e = e.twin_edge.next_edge

class Edge(object):
    def __init__(self, origin_vertex):
        super(Edge, self).__init__()
        self.origin_vertex = origin_vertex
        self.twin_edge = None
        self.next_edge = None
        self.prev_edge = None
        self.face = None
        
    def dest_vertex(self):
        return self.twin_edge.origin_vertex

    def go_up(self):
        return self.origin_vertex.point.y > self.dest_vertex().point.y

    def go_down(self):
        return self.twin_edge.go_up()

    def horizontal(self):
        return not self.go_up() and not self.go_down()

    def in_open(self):
        e = self.next_edge
        twin = self.twin_edge
        while e != self and e != twin:
            e = e.next_edge
        return e == twin


class Face(object):
    def __init__(self, edge):
        super(Face, self).__init__()
        self.edge = edge

    def vertices(self):
        o = e = face.edge
        
        yield e.origin_vertex
        e = e.next_edge
        
        while e != o:
            yield e.origin_vertex
            e = e.next_edge
            
class DoubleConnectedEdgeList(object):
    def __init__(self):
        super(DoubleConnectedEdgeList, self).__init__()
        self.faces = set()

    @classmethod
    def create_twin_edges(cls, v1, v2):
        e1 = Edge(v1)
        e2 = Edge(v2)
        e1.twin_edge = e2
        e2.twin_edge = e1
        return e1, e2

    @classmethod
    def find_vertex(cls, vertices, point):
        for vertex in vertices:
            if vertex.point == point:
                return vertex
        return None

    def add_face(self, edge):
        f = Face(edge)
        self.faces.add(f)
        edge.face = f

    def get_vertices(self):
        vertices = set()
        for face in self.faces:
            vertices.add(face.vertices())
        return vertices

    def get_vertices_ordered(self):
        vertices = orderedset()
        for face in self.faces:
            vertices.add(face.vertices())
        return vertices

    
    def fix_faces(self, e1):
        remove_faces = set()
        f1 = e1.face
        e = e1.next_edge
        while e != e1:
            remove_faces.add(e.face)
            e.face = f1
            e = e.next_edge
        self.faces.remove(remove_faces)
        self.faces.add(f1)

        
def build_dcel(segments):
    dcel = DoubleConnectedEdgeList()
    vertices = [] # just to find other vertices quicker when creating the dcel
    for segment in segments:
        p1, p2 = segment.p1, segment.p2

        v1 = dcel.find_vertex(vertices, p1)
        v2 = dcel.find_vertex(vertices, p2)

        ###################################################################
        # split_v1 = v1 is not None                                       #
        # split_v2 = v2 is not None                                       #
        #                                                                 #
        # if v1 is None:                                                  #
        #     v1 = Vertex(p1)                                             #
        # if v2 is None:                                                  #
        #     v2 = Vertex(p2)                                             #
        # e1, e2 = dcel.create_twin_edges(v1, v2)                         #
        #                                                                 #
        # if split_v1:                                                    #
        #     e1.prev_edge = first_counter_clockwise_edge_of_v1.twin_edge #
        #     e2.next_edge = first_clockwise_edge_of_v1#.edge             #
        # if split_v2:                                                    #
        #     e1.next_edge = first_clockwise_edge_of_v2#.edge             #
        #     e2.prev_edge = first_counter_clockwise_edge_of_v2.twin_edge #
        #                                                                 #
        # e1.prev_edge.next_edge = e1                                     #
        # e2.next_edge.prev_edge = e2                                     #
        # e1.next_edge.prev_edge = e1                                     #
        # e2.prev_edge.next_edge = e2                                     #
        #                                                                 #
        #                                                                 #
        # # check if we didnt closed a loop by going through the          #
        # # path of the edges, starting from e1, and see if we            #
        # # get e2. if we find e2 this means we didnt closed a            #
        # # loop. otherwise, we closed a loop, and we should create       #
        # # a new face                                                    #
        # if not split_v1 and not split_v2:                               #
        #     e1.face = dcel.add_face(e1)                                 #
        #                                                                 #
        # f1 = e1.face                                                    #
        # f1.edge = e1 # just make sure we didnt left an edge from face2  #
        #                                                                 #
        # e = e1.next_edge                                                #
        # while e != e1 and e != e2:                                      #
        #     e.face = f1                                                 #
        #     e = e.next_edge                                             #
        # if e == e1:                                                     #
        #     # we closed a loop, so create a new face                    #
        #     e2.face = f2 = dcel.add_face(e2)                            #
        #     f2.edge = e2                                                #
        #                                                                 #
        #     # set all the others faces in the e2 loop                   #
        #     e = e2.next_edge                                            #
        #     while e != e2:                                              #
        #         e.face = f2                                             #
        #         e = e.next_edge                                         #
        # else: # if e == e2 -> we didnt closed a loop                    #
        #     while e != e1:                                              #
        #         e.face = f1                                             #
        #         e = e.next_edge                                         #
        ###################################################################
            
        
            
        # as a convention, e1 will leave from p1 to p2 (v1 to v2), and e2 (the twin) will leave from p2 to p1 (v2 to v1)
        # also, next will be always clockwise, and prev will be counter clockwise. this way we wont get mobius strip
        # this means that the trip on the edges will be counter clockwise
        if v1 is None and v2 is None:
            # create a new face, create 2 new edges and create 2 vertices
            v1 = Vertex(p1)
            v2 = Vertex(p2)
            e1, e2 = dcel.create_twin_edges(v1, v2)
            
            f = dcel.add_face(e1)
            v1.edge = e1
            v2.edge = e2
            
            e1.next_edge = e2
            e1.prev_edge = e2
            e1.face = f

            e2.next_edge = e1
            e2.prev_edge = e1
            e2.face = f

        elif v1 is not None and v2 is None:
            # create 2 new edges, create 1 vertex
            v2 = Vertex(p2)
            e1, e2 = dcel.create_twin_edges(v1, v2)
            v2.edge = e2
            
            e1.next_edge = e2
            e2.prev_edge = e1
            
            e1.prev_edge = first_counter_clockwise_edge_of_v1.twin_edge
            e2.next_edge = first_clockwise_edge_of_v1#.edge
            
            e1.prev_edge.next_edge = e1
            e2.next_edge.prev_edge = e2

            
            e1.face = e1.prev_edge.face
            e2.face = e2.next_edge.face
            


        elif v1 is None and v2 is not None:
            # create 2 new edges, create 1 vertex
            v1 = Vertex(p1)
            e1, e2 = dcel.create_twin_edges(v1, v2)
            v1.edge = e1
            
            e1.prev_edge = e2
            e2.next_edge = e1
            
            e1.next_edge = first_clockwise_edge_of_v2#.edge
            e2.prev_edge = first_counter_clockwise_edge_of_v2.twin_edge
            
            e1.next_edge.prev_edge = e1
            e2.prev_edge.next_edge = e2
            

            e1.face = e1.next_edge.face
            e2.face = e2.prev_edge.face
            

            
        elif v1 is not None and v2 is not None:
            # create 2 edges and connect them, then, if we closed a loop split the face (so a new face will be created)
            
            # first, find the face of the 2 vertices
            e1, e2 = dcel.create_twin_edges(v1, v2)
            
            e1.next_edge = first_clockwise_edge_of_v2#.edge
            e2.prev_edge = first_counter_clockwise_edge_of_v2.twin_edge
            
            e1.prev_edge = first_counter_clockwise_edge_of_v1.twin_edge
            e2.next_edge = first_clockwise_edge_of_v1#.edge

            e1.next_edge.prev_edge = e1
            e2.prev_edge.next_edge = e2

            e1.prev_edge.next_edge = e1
            e2.next_edge.prev_edge = e2

            f1 = e1.face = e1.next_edge.face
            f2 = e2.face = e2.next_edge.face

            f1.edge = e1 # just make sure we didnt left an edge from face2
            
            #assert e1.face == e2.face

            # check if we didnt closed a loop by going through the 
            # path of the edges, starting from e1, and see if we 
            # get e2. if we find e2 this means we didnt closed a 
            # loop. otherwise, we closed a loop, and we should create 
            # a new face
            if not e.in_open():
                # we closed a loop, so create a new face
                dcel.add_face(e2)
                
                dcel.fix_faces(e2)
                # set all the others faces in the e2 loop
                #e = e2.next_edge
                #while e != e2:
                #    remove_faces.add(e.face)
                #    e.face = f2
                #    e = e.next_edge
            else: # if e == e2 -> we didnt closed a loop
                dcel.fix_faces(e1)
            
    return dcel

def merge_dcel(dcel1, dcel2):
    vertices1 = sorted(list(dcel1.get_vertices()), key = lambda v: v.point.y)
    vertices2 = sorted(list(dcel2.get_vertices()), key = lambda v: v.point.y)

    i1 = 0 # dcel1 scan line
    i2 = 0 # dcel2 scan line

    edges1 = set()
    edges2 = set()

    dcel = DoubleConnectedEdgeList()

    #    final_edges = set()

    while i1 < len(vertices1) and i2 < len(vertices2):
        if vertices1[i1].point.y < vertices2[i2].point.y:
            # TODO: check when to remove unneeded edges. should remove edges if their lower vertex is higher then current enumerated vertex
            # TODO: not needed because if edge2.higher_y is smaller than edge1.lower_y then we finished handling it
            for edge1 in vertices1[i1].edges():
                if edge1.go_down():
                    # start handling edge
                    edges1.add(edge1)
                elif edge1.go_up():
                    # edge which going up or horizontal edge. end handling edge
                    edges1.remove(edge1)
                    intersections = False
                    for edge2 in edge1.intersects(edges2):
                        # notice edge2 must go down, and its lower point is under edge1. otherwise, we would handle it before edge1
                        
                        intersections = True
                        # for each intersection add a vertex
                        intersection_point = edge1.intersect(edge2)
                        p11 = edge1.origin_vertex # top left
                        p12 = edge1.dest_vertex() # bottom right
                        p21 = edge2.origin_vertex # top right
                        p22 = edge2.dest_vertex() # bottom left
                        v = Vertex(intersection_point)
                        
                        e11_v1, e11_v2 = DoubleConnectedEdgeList.create_twin_edges(v, p11)
                        e12_v1, e12_v2 = DoubleConnectedEdgeList.create_twin_edges(v, p12)
                        e21_v1, e21_v2 = DoubleConnectedEdgeList.create_twin_edges(v, p21)
                        e22_v1, e22_v2 = DoubleConnectedEdgeList.create_twin_edges(v, p22)

                        # notice we have 4 faces to use - of edge1, edge1.twin, edge2, edge2.twin
                        
                        # top left
                        e11_v1.next_edge = clockwise_p11
                        e11_v1.prev_edge = e22_v2
                        e11_v1.face = e11_v1.next_edge.face
                        e11_v1.next_edge.prev_edge = e11_v1
                        dcel.fix_faces(e11_v1)

                        e11_v2.next_edge = e21_v1
                        e11_v2.prev_edge = counter_clockwise_p11
                        e11_v2.face = e11_v2.prev_edge.face
                        e11_v2.next_edge.prev_edge = e11_v2
                        dcel.fix_faces(e11_v2)

                        # top right
                        e21_v1.next_edge = clockwise_p21
                        e21_v1.prev_edge = e11_v2
                        e21_v1.face = e21_v1.next_edge.face
                        e21_v1.next_edge.prev_edge = e21_v1
                        dcel.fix_faces(e21_v1)

                        e21_v2.next_edge = e12_v1
                        e21_v2.prev_edge = counter_clockwise_p21
                        e21_v2.face = e21_v2.prev_edge.face
                        e21_v2.next_edge.prev_edge = e21_v2
                        dcel.fix_faces(e21_v2)

                        # bottom right
                        e12_v1.next_edge = clockwise_p12
                        e12_v1.prev_edge = e21_v2
                        e12_v1.face = e12_v1.next_edge.face
                        e12_v1.next_edge.prev_edge = e12_v1
                        dcel.fix_faces(e12_v1)

                        e12_v2.next_edge = e22_v1
                        e12_v2.prev_edge = counter_clockwise_p12
                        e12_v2.face = e12_v2.prev_edge.face
                        e12_v2.next_edge.prev_edge = e12_v2
                        dcel.fix_faces(e12_v2)

                        # bottom left
                        e22_v1.next_edge = clockwise_p22
                        e22_v1.prev_edge = e12_v2
                        e22_v1.face = e22_v1.next_edge.face
                        e22_v1.next_edge.prev_edge = e22_v1
                        dcel.fix_faces(e22_v1)

                        e22_v2.next_edge = e11_v1
                        e22_v2.prev_edge = counter_clockwise_p22
                        e22_v2.face = e22_v2.prev_edge.face
                        e22_v2.next_edge.prev_edge = e22_v2
                        dcel.fix_faces(e22_v2)

#                    if not intersections:
#                        final_edges.add(edge1)
            i1 += 1
        if vertices1[i1].point.y > vertices2[i2].point.y:
            # do same as when i1 += 1
            i2 += 1
        else:
            if vertices1[i1].point.x == vertices2[i2].point.x:
                v = vertices1[i1]
                # dont create any edges here, use the existing
                vertex_edges1 = vertices1[i1].edges()
                vertex_edges2 = vertices2[i2].edges()

                vertex_edges = []
                for e in vertex_edges1:
                    if e.go_down()
                        edges1.add(e)
                    else:
                        vertex_edges.add(e)
                for e in vertex_edges1:
                    if e.go_down()
                        edges2.add(e)
                    else:
                        vertex_edges.add(e)

                vertex_edges = sorted(vertex_edges, polaric_order)
                prev_e = counter_clockwise_of_v_from_first_in_vertex_edges
                for e1, e2 in zip(vertex_edges, vertex_edges[1:]):
                    #e1.next_edge = e2
                    e1.prev_edge = prev_e
                    e1.face = e1.next_edge.face
                    e1.prev_edge.next_edge = e1
                    dcel.fix_faces(e1)

                    e1tag = e1.twin_edge

                    e1tag.next_edge = e2
                    #e1.prev_edge = prev_e
                    e1tag.face = e1tag.prev_edge.face
                    e1tag.next_edge.prev_edge = e1tag
                    dcel.fix_faces(e1tag)

                    prev_e = e1
                    
                    edges1.remove(e1)
                    
                elast = vertex_edges[-1]
                elast.prev_edge = clockwise_of_v.twin_edge
                elast.face = elast.next_edge.face
                elast.prev_edge.next_edge = elast
                dcel.fix_faces(elast)

                elasttag = elast.twin_edge
                elasttag.next_edge = clockwise_of_v
                elasttag.face = elasttag.next_edge.face # should be like elasttag.prev_edge.face
                elasttag.next_edge.prev_edge = elasttag
                dcel.fix_faces(elasttag)

            else:
                # do exacly like i do when i1 += 1 and i2 += 1, for both vertices
            # do something
            i1 += 1
            i2 += 1

def find_point_dcel(dcel, point):
    vertices = sorted(list(dcel.get_vertices()), key = lambda v: v.point.y)

    edges = set()
    for vertex in vertices:
        if point.y < vertex.point.y:
            break
        for edge in vertex.edges():
            if edge.go_down():
                # start handling edge
                edges.add(edge)
            elif edge.go_up():
                # edge which going up or horizontal edge. end handling edge
                edges.remove(edge)

    # now, order the edges in edge by their x values in y.
    # actually, we dont need to order, but just to get the smallest dx
    min_dx = None
    min_face = None
    for edge in edges:
        p1 = edge.origin_vertex.point
        p2 = edge.dest_vertex().point

        # y = ax + b => x = (y - b) / a
        # y = (y1 - y2) / (x1 - x2) * x + b => a = dy / dx
        # b = y1 - (y1 - y2) / (x1 - x2) * x1 = (y1 * (x1 - x2) - x1 * (y1 - y2)) / (x1 - x2) = (y1 * dx - x1 * dy) / dx
        # x = (y - (y1 * dx - x1 * dy) / dx) / (dy / dx) = (y - (y1 * dx - x1 * dy) / dx) * (dx / dy)
        # x = y * dx / dy - (y1 * dx - x1 * dy) / dy
        # x = (y - y1) * dx / dy + x1
        # x * dy = (y - y1) * dx + x1 * dy
        # (x - x1) * dy = (y - y1) * dx

        # dx_tag = point.x - edge_x_in_y
        # but to get edge_x_in_y we will have to divide something in dy
        # so instead of dividing, we will look for the smallest
        # dx_tag * dy = point.x * dy - (y - y1) * dx + x1 * dy
        # dx_tag * dy = (point.x + x1) * dy - (y - y1) * dx
        # dx_tag = (point.x + x1) - (y - y1) * dx / dy
        x1 = p1.x
        x2 = p2.x
        dx = x1 - x2
        dy = p1.y - p2.y
        if (point.x + x1) > (y - y1) * dx / dy:
            dx_tag = (point.x + x1) - (y - y1) * dx / dy
        else:
            dx_tag = ((y - y1) * dx - (point.x + x1) * dy) / dy
        if min_dx is None or dx_tag < min_dx:
            min_dx = dx_tag
            min_face = edge.face
    return min_face

def intersect_closed_convex_dcel_slow(dcel1, dcel2):
    # since its closed convex, the result will be one face only.
    # so we join the dcel, and go over the joined faces. we will find any point inside the face of the original, and look for its face in the merged

    # find a point in dcel1. any point
    edge = dcel1.face.edge
    p1 = edge.point
    p2 = edge.dest_vertex().origin_point
    p3 = edge.next_edge.origin_point # the counter clockwise of edge1 to vertices1[i1]

    point = any_point_in_triangle(Triangle(p1, p2, p3))
    
    # this will destroy dcel1 and dcel2
    dcel = merge_dcel(dcel1, dcel2)

    return find_point_dcel(dcel, point)

    
def intersect_closed_convex_dcel(dcel1, dcel2):
    vertices1 = sorted(list(dcel1.get_vertices()), key = lambda v: v.point.y)
    vertices2 = sorted(list(dcel2.get_vertices()), key = lambda v: v.point.y)

    i1 = 0 # dcel1 scan line
    i2 = 0 # dcel2 scan line

    edges1 = set()
    edges2 = set()

    dcel = DoubleConnectedEdgeList()

    #    final_edges = set()
    
    intersection_points = []

    while i1 < len(vertices1) and i2 < len(vertices2):
        p1 = vertices1[i1].point
        p2 = vertices2[i2].point
        if p1.y < p2.y:
            for edge1 in vertices1[i1].edges():
                if edge1.go_down():
                    # start handling edge
                    edges1.add(edge1)
                elif edge1.go_up():
                    edges1.remove(edge1)
                    
            right_most_edge = None
            left_most_edge = None
            for edge2 in edges2:
                segment = Segment(edge2.origin_vertex, edge2.dest_vertex())
                if point_left_of_segment(p1, segment) == TwoPointSide.SAME_SIDE:
                    if right_most_edge is None or segment_compare(right_most_edge, edge2) == SegmentCompare.RIGHT:
                        right_most_edge = edge2
                elif point_left_of_segment(p2, segment) == TwoPointSide.DIFFERENT_SIDE:
                    if left_most_edge is None or segment_compare(left_most_edge, edge2) = SegmentCompare.LEFT:
                        left_most_edge = edge2
                        
            if right_most_edge is not None and left_most_edge is not None:
                intersection_points.append(p1)
            
            i1 += 1
        
        elif p1.y > p2.y:
            # do the same thing as p1.y < p2.y
            i2 += 1
            
    return intersection_points